package com.xzz.greedy;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2022-01-12 15:19
 * 45. 跳跃游戏 II
 * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 假设你总是可以到达数组的最后一个位置。
 *
 **/
public class Jump {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{2,3,1,1,4}));
        System.out.println(jump(new int[]{3,2,1}));
    }
    static int[] memo;
    public static int jump(int[] nums) {
//        memo = new int[nums.length];
//        Arrays.fill(memo,nums.length);
//        return dp(nums,0);

        int res = 0;
        int end = 0;
        int jumps = 0;
        for (int i = 0; i < nums.length-1; i++) {
            res = Math.max(res,i+nums[i]);
            if(end == i){
                jumps++;
                end = res;
            }
        }
        return jumps;
    }
    //从j跳到最后一个的最小步数
    public static int dp(int[] nums,int j){
        if(j>=nums.length-1){
            return 0;
        }
        if(memo[j]!=nums.length){
            return memo[j];
        }
        int len = nums[j];
        for (int i = 1; i <= len; i++) {
            int temp = dp(nums,j+i);
            memo[j] = Math.min(temp+1,memo[j]);
        }
        return memo[j];
    }
}
